// //数字迷宫
// #include <bits/stdc++.h>
// using namespace std;

// int a[11][11];
// int N,K;
// bool vis[11][11];
// int dx[8] = {0,1,1,1,0,-1,-1,-1};
// int dy[8] = {-1,-1,0,1,1,1,0,-1};
// string ret;
// bool is = false;
// void dfs(int row , int col , int pre , int count,string path)
// {
//     if(a[row][col] != pre) return;
//     if(!is  && row == N && col == N && count == N*N)
//     {
//         ret = path;
//         is = true;
//         return;
//     }
    
    
//     for(size_t i = 0 ; i < 8 ; ++i)
//     {
//         int y = row + dy[i],x = col + dx[i];
//         if(y >= 1 && x >= 1 && y <= N && x <= N && vis[y][x] == false)
//         {
//             //判断交线
//             if(i == 1 && vis[row-1][col] && vis[row][col+1]) continue;
//             if(i == 3 && vis[row+1][col] && vis[row][col+1]) continue;
//             if(i == 5 && vis[row][col-1] && vis[row+1][col]) continue;
//             if(i == 7 && vis[row-1][col] && vis[row][col-1]) continue;
//             vis[y][x] = true;
//             cout << y << " " << x << endl;
//             dfs(y,x,(a[row][col]+1)%K,count+1,path+to_string(i));
//             vis[y][x] = false;
//         }
//     }
// }
// int main()
// {
//     cin >> N >> K;
//     for(size_t i = 1 ; i <= N ; ++i)
//         for(size_t j = 1 ; j <= N ; ++j)
//             cin >> a[i][j];
//     string path;
//     vis[1][1] = true;
//     dfs(1,1,0,1,path);
//     vis[1][1] = false;
//     if(ret.empty()) cout << -1 << endl;
//     else 
//     {
//         cout << ret << endl;
//     }
//     return 0;
// }

//R格式
// #include<bits/stdc++.h>
// using namespace std;
// int GetPow(int num)
// {
//     int temp = 1;
//     for(size_t i = 0 ; i < num ; ++i) temp *= 2;

//     return temp;
// }
// bool IsNext(double d)
// {
//     d *= 10;
//     int val = d;
//     d -= val;
//     if(val  < 4) return false;
//     else if(val > 4) return true;
//     else 
//     {
//         if(IsNext(d)) return true;
//         else return false; 
//     }
// }

// int main()
// {
//     int n;
//     double d;
//     cin >> n;
//     cin >> d;
//     int num = GetPow(n);
//     d *= num;
//     int num = d;//取出整数部分
//     d -= num;//取出小数部分
//     if(IsNext(d))//判断是否进位
//     {
//         num ++;
//     }
//     cout << num << endl;
//     return 0;
// }

//解码异或后的数组
class Solution {
public:
    vector<int> decode(vector<int>& encoded, int first) {
        int n = encoded.size();
        vector<int> arr(n+1);
        arr[0] = first;
        //encoded[i] = arr[i] ^ arr[i-1]
        //arr[i] = encoded[i] ^ arr[i-1]
        for(int i = 1 ; i <= n ; ++i)
        {
            arr[i] = encoded[i-1] ^ arr[i-1];
        }
        return arr;
    }
};

//可能的二分法
class Solution {
public:
    enum
    {
        RED = 1,
        BLUE
    };
    int GetNextColor(int color)
    {
        if(color == RED) return BLUE;
        else if(color == BLUE) return RED;
        return -1;
    }
    bool dfs(vector<int>& colors , int curNode , int color , vector<vector<int>>& v)
    {
        colors[curNode] = color;
        for(auto& nextNode : v[curNode])
        {
            if(colors[nextNode] && colors[nextNode] == colors[curNode]) return false;
            if(!colors[nextNode] && dfs(colors,nextNode,GetNextColor(color) ,v) == false) return false;
        }
        return true;
    }
    bool possibleBipartition(int n, vector<vector<int>>& dislikes) {
       vector<int> color(n+1); // 0：未被染色，1：被染成了红色，2：被染成了蓝色
       vector<vector<int>> v(n+1);
       for(auto& e : dislikes)
       {
        //保存所有的仇人节点
            v[e[0]].push_back(e[1]);
            v[e[1]].push_back(e[0]);
       }
       for(int i = 1 ; i <= n ; ++i)
       {
            if(color[i] == 0 && dfs(color,i,BLUE,v) == false) return false;
       }
       return true;
    }
};